Microscopic Crowd Simulation:
Evaluation and Development of Algorithms

David Wolinski

Supervised by: Julien Pettré

Introduction - Crowd Simulation

Introduction
Crowd Simulation
Entertainment
  • movies
  • video games

Figure: Lord of the Rings.

Figure: World War Z.

Figure: Dynasty Warriors.

Figure: Assassin's Creed.

Urbanism
  • architecture
  • security

Figure: Mall (Złote Tarasy, Poland).

Figure: Disney World.

Figure: Cruise Ship (Costa Concordia).

Figure: Stadium (Kaiserslautern, Germany).

Introduction - Requirements

Introduction
Requirements
Entertainment
  • Movies:
    • Believability
    • High level of control
  • Video games:
    • Believability and control
    • Interactable characters
Urbanism
  • Architecture:
    • Accuracy
    • Autonomy
  • Security:
    • Accuracy and autonomy
    • Quick adaptability
Summary - Four main questions
  • Performance easy
  • Control more difficult
  • Autonomy more difficult
  • Realism difficult

Introduction - Objectives

Introduction
Objectives
The focus of this thesis: realism.
Two main objectives:
Evaluation
Design a generally applicable evaluation scheme.
Simulation
Develop improved simulation algorithms.

Outline

Outline
1 - Related Work
2 - Two main contributions:
Evaluation
An evaluation framework
automatic tuning of algorithms -
data-based -
general -
Simulation
New collision-avoidance algorithm
- advanced collision prediction
- probabilistic
- easily extensible
3 - Secondary contributions:
Applications of evaluation framework
- insect simulation
- pedestrian tracking

Related Work

Related Work - Crowd Simulation Algorithms - Animation

Related Work
Crowd Simulation Algorithms - Animation
Data-driven algorithms

Figure: Learning pipeline [CC14].

Tiles and patches

Figure: Crowd tiles [Che04].

Figure: Crowd patches [YMPT09].

Related Work - Crowd Simulation Algorithms - Prediction

Related Work
Crowd Simulation Algorithms - Prediction
Macroscopic algorithms

Figure: Result from [TCP06].

Figure: Result from [NGCL09].

Cellular automata

Figure: Conflict between two characters on a grid [Sch01].

Related Work - Crowd Simulation Algorithms - Prediction

Related Work
Crowd Simulation Algorithms - Prediction
Agent-based simulation
  • define interactions between characters (agents)
  • crowds assembled from interacting agents
  • flexible
=> The focus of this thesis.
Most fundamental behavior: collision avoidance.

Related Work - Agent-Based Simulation Algorithms

Related Work
Agent-Based Simulation Algorithms
First-Order
Agent interactions are computed from their positions.
  • Boids [Rey87]
  • Social Forces [HM95]
Agents interact with each other following three rules:

Figure: Alignment.

Figure: Cohesion.

Figure: Separation.

  • Boids [Rey87]
  • Social Forces [HM95]
Agents repulse each other based on their proximity:
$$ \frac{d\overrightarrow{v}_\alpha}{dt} = \overrightarrow{F}_\alpha (t) + fluctuations $$
  • Boids [Rey87]
  • Social Forces [HM95]
  • These simple rules already allow for convincing overall behaviors.
  • But many artifacts remain:
    • late reactions,
    • pathological cases,
    • instabilities at high densities,
    • etc.

Related Work - Agent-Based Simulation Algorithms

Related Work
Agent-Based Simulation Algorithms
Second-Order
Agent interactions are computed from their positions and velocities.
  • Closest approach
  • Admissible velocities
  • Other methods
Explicitly compute agents' positions when closest to each-other.

Figure: [Rey99]

Figure: [KHBO09]

Figure: [PESVG09]

  • Closest approach
  • Admissible velocities
  • Other methods
Determine which velocities allow collision-free motion.

Figure: [PPD07]

Figure: [vdBLM08]

Figure: [POO+09]

  • Closest approach
  • Admissible velocities
  • Other methods

Figure: [KSHF09]

Figure: [OPOD10]

Figure: [KSG14]

  • Closest approach
  • Admissible velocities
  • Other methods
  • Much improved over first-order algorithms.
  • limited by the linear extrapolation of agents' motions.
  • Some issues remain:
    • oscillations,
    • saturation of solution space,
    • lockdowns,
    • etc.

Related Work - Evaluation

Related Work
Evaluation
Qualitative observation.

Figure: [HFV00]

Figure: [OPOD10]

  • easy
  • not very rigorous
Quantitative evaluation: metrics.

Figure: [CSC09]

Figure: [GvdBL+12]

  • rigorous

Related Work - Evaluation

Related Work
Evaluation
Benchmarks, frameworks.

Figure: [SKFR09]

  • many test-cases, metrics
  • not based on data

Figure: [LCSCO10]

  • data-based

Related Work - Parameters

Related Work
Parameters
What about parameters?
  • size of agents, cautiousness, preferred velocity, etc.
  • absurd values lead to wrong results
  • can also be the case with default values
Approaches
  • Most commonly, by manual tweaking: imprecise and tedious
  • Recently: some automation.
    • gradient descent and genetic algorithm [PESVG09]
    • Maximum Likelihood Estimation [POO+09]
    • Regression [KSG14]
Not systematically taken care of.

Related Work - Summary

Related Work
Summary
Agent-Based Simulation
  • current algorithms use:
    • positions
    • velocities
  • limited by the linear anticipation
  • simulation issues remain
Evaluation
  • no standardized, data-based approach
  • parameters usually not taken care of

Outline

Outline
1 - Related Work
2 - Two main contributions:
Evaluation
An evaluation framework
automatic tuning of algorithms -
data-based -
general -
Simulation
New collision-avoidance algorithm
- advanced collision prediction
- probabilistic
- easily extensible
3 - Secondary contributions:
Applications of evaluation framework
- insect simulation
- pedestrian tracking

Craal: Parameter Estimation and Comparative Evaluation of Crowd Simulations

Introduction

Introduction
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Existing Work
  • no standardized approach to evaluation
  • algorithms' parameters not systematically taken care of
The problem:
A comparison between a simulation and some data.
Same algorithm,
different parameters.

Introduction

Introduction
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Existing Work
  • no standardized approach to evaluation
  • algorithms' parameters not systematically taken care of
We propose:

Overview - Formulation

Overview
Formulation
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
A simulation algorithm:
$$ \begin{align} \left[\begin{array}{c}\mathbf{x}_{k+1} \\ \mathbf{v}_{k+1} \end{array}\right] & = f(\mathbf{x}_k,\mathbf{v}_k,\mathbf{g}). \end{align} $$
A parameterized algorithm:
$$ \begin{align} \left[\begin{array}{c}\mathbf{x}_{k+1} \\ \mathbf{v}_{k+1} \end{array}\right] & = f(\mathbf{x}_k,\mathbf{v}_k,\mathbf{g},\color{red}{\mathbf{p}}). \end{align} $$
The reference data is a collection of observations:
$$ \begin{align} \color{red}{\mathbf{z}} = \bigcup_{k=1}^m \mathbf{z}_k. \end{align} $$
A corresponding simulation:
$$ \begin{align} \color{red}{f(\mathbf{z}, \mathbf{p})} = \bigcup_{k=1}^m f(\mathbf{x}_k, \mathbf{v}_k, \mathbf{g}, \mathbf{p}). \end{align} $$
Given a distance metric, the optimal parameters:
$$ \DeclareMathOperator*{\argmin}{argmin} \begin{align} \color{red}{\mathbf{p}^{opt, f}} & = \argmin_{\mathbf{p}} dist(f(\mathbf{z},\mathbf{p}),\mathbf{z}). \end{align} $$
Comparison of two algorithms:
$$ \begin{align} dist(\color{red}{f_1}(\mathbf{z},\color{red}{\mathbf{p}^{opt, f_1}}),\mathbf{z}) < dist(\color{blue}{f_2}(\mathbf{z},\color{blue}{\mathbf{p}^{opt, f_2}}),\mathbf{z}). \end{align} $$

We need... - Metrics

We need...
Metrics
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Microscopic Data Metrics
  • absolute difference metric
  • path length metric
  • inter-pedestrian distance metric
  • progressive difference metric
Macroscopic Data Metrics
  • vorticity metric
  • fundamental diagram metric
Detailed description in manuscript.

We need... - Optimization algorithms

We need...
Optimization algorithms
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
We have
  • noisy cost functions (metrics)
  • very high-dimensional search-spaces (each agent has its own set of parameters)
  • Greedy approach: good start, but gets "stuck" in local optima
  • Simulated annealing[KGV83]:
    • with enough time, theoretically guaranteed global optimum
    • used as a baseline to compare other optimization algorithms
  • Genetic algorithm[Hol92] and Covariance Matrix Adaptation[HO96]: two evolutionary, pool-based algorithms

We need... - Optimization algorithms

We need...
Optimization algorithms
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Comparison of optimization algorithms
  • results in the manuscript
  • genetic+greedy offered the best compromise between speed and score improvement
  • all presented results use the genetic+greedy approach

Figure: Results in manuscript.

Example optimization

Example optimization
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Uses Difference metric: distance between real and simulated trajectories.

Results - Microscopic, complete data

Results
Microscopic, complete data
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Data
  • motion captured
  • moderate amounts of pedestrians
  • complete knowledge of pedestrans' trajectories

Results - Microscopic data

Results
Microscopic data
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Dataset: 2-5 pedestrians interacting in various ways.
Red: reference
Blue: simulated

Results - Microscopic data

Results
Microscopic data
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Dataset: 2-5 pedestrians interacting in various ways.
Red: reference
Blue: simulated

Results - Microscopic data

Results
Microscopic data
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Dataset: 6-24 pedestrians in a circle, goal is to get to antipodal position.
Red: reference
Blue: simulated

Results - Microscopic, incomplete data

Results
Microscopic, incomplete data
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Data
  • tracked with overhead cameras
  • possibly many pedestrians
  • incomplete knowledge of pedestrans' trajectories

Results - Microscopic, incomplete data

Results
Microscopic, incomplete data
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Dataset: crossing flows of pedestrians (∼150).
Red: reference
Blue: simulated

Results - Macroscopic data

Results
Macroscopic data
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Data
  • statistical data
  • independent of the number of pedestrians
  • example: fundamental diagram

Results - Macroscopic data

Results
Macroscopic data
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion

Figure: Original data [CSC09].

  • relation between density and speed
  • here: cultural differences between Germans and Indians

Results - Macroscopic data

Results
Macroscopic data
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion

Figure: Boids-like algorithm fit to the diagram.

  • lines: idealized original data
  • crosses/squares: simulation data

Results - Macroscopic data

Results
Macroscopic data
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion

Figure: Various algorithms fit to the diagram.

  • Boids-like algorithm poorly fits the data
  • Social-force and RVO2 fit much better
  • Social-force agents are too fast at high densities

Results - Macroscopic data

Results
Macroscopic data
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Corresponding animation.

Results - Benchmarks

Results
Benchmarks
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
All results can be summarized in a benchmark fashion:

Results - Benchmarks

Results
Benchmarks
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
All results can be summarized in a benchmark fashion:

Results - Sketch-like data

Results
Sketch-like data
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Bonus case
  • animation context
  • made-up (e.g. by artists)
  • for a specific target motion

Results - Sketch-like data

Results
Sketch-like data
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Example: vortex-like motion.

Results - Sketch-like data

Results
Sketch-like data
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Example: grouped agents, then dispersed, then regrouped.

Results - Sketch-like data

Results
Sketch-like data
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Animation
  • classically:
    • individual agent waypoints
    • manual parameter tweaking
  • with the system: automatic initial proposition

Summary

Summary
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Summary
  • simulators’ parameters greatly affect simulation results
  • compute the parameters to best fit the data, given a metric
  • use these parameters when comparing simulation algorithms
  • the framework is general:
    • data
    • metrics
    • simulators

Limitations, future work

Limitations, future work
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Limitations
  • search-space is very high-dimensional
  • the optimization is still time-consuming
  • performance heavily depends on the implementation of metrics and simulators
  • easy to parallelize when doing multiple comparisons

Limitations, future work

Limitations, future work
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Future work
  • how representative is the data?
    • are there some "good enough", general parameters?
  • what about the metrics?
    • define metrics well adapted to various scenarios

Outline

Outline
1 - Related Work
2 - Two main contributions:
Evaluation
An evaluation framework
automatic tuning of algorithms -
data-based -
general -
Simulation
New collision-avoidance algorithm
- advanced collision prediction
- probabilistic
- easily extensible
3 - Secondary contributions:
Applications of evaluation framework
- insect simulation
- pedestrian tracking

WarpDriver: Context-Aware Probabilistic Motion Prediction for Crowd Simulation

Introduction

Introduction
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
A toy example:

Introduction

Introduction
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
A toy example:
Typical second-order algorithm.

Introduction

Introduction
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
A toy example:
Typical second-order algorithm.
But:
  • A won't continue moving straight

Introduction

Introduction
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
A toy example:
Typical second-order algorithm.
But:
  • A won't continue moving straight
  • B & C could also turn
A combinatorial approach would be too expensive.

Introduction

Introduction
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
A toy example:
Top-down view.
Perspective view.
Instead: a probabilistic approach.
  • in 3D space-time (2D positions + time)

Introduction

Introduction
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
A toy example:
Top-down view.
Perspective view.
Instead: a probabilistic approach.
  • in 3D space-time (2D positions + time)
  • estimate collision probabilities

Introduction

Introduction
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
A toy example:
Top-down view.
Perspective view.
Instead: a probabilistic approach.
  • in 3D space-time (2D positions + time)
  • estimate collision probabilities
  • move accordingly

Overview

Overview
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Top-down view.
Perspective view.
Simplifications:
  • perceiving agent moves in configuration space:
    • reduced to a point
    • other agents perceived as Minkowski sum
  • deal with each agent separately
  • deal with each agent property separately

Overview

Overview
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Top-down view.
Perspective view.
1 - Projected trajectory.
Projected trajectory of the perceiving agent:
$$ \mathbf{r}_{a, k} = line(\mathbf{o},\: v_{a, k} \mathbf{x} + \mathbf{t}), $$

Overview

Overview
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Top-down view.
Perspective view.
1 - Intrinsic field.
  • ignores agents' properties
  • only models agents' co-existence
$$ \forall \mathbf{s}=(x, y, t) \in \mathcal{S}_{b, k}, $$
Minkowski sum:
$$ g(\mathbf{s}) = \begin{cases} 1, & \text{if } \sqrt{x^2 + y^2} \leq 1\\ 0, & \text{otherwise} \end{cases} $$
Perception error:
$$ f(\mathbf{s}) = exp(-(\frac{x^2 + y^2}{2\sigma^2})) $$
Intrinsic field:
$$ I(\mathbf{s}) = (f*g)(\mathbf{s}) $$

Overview

Overview
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Top-down view.
Perspective view.
2 - Warp operators.
  • model agents' properties
  • 1 property = 1 operator
  • cumulatively deform intrinsic field
Operators:
$$ \{ W_1, ..., W_n \} $$
Composition:
$$ \mathbf{W} = W_n \circ ... \circ W_1, \\ \mathbf{W}^{-1} = W_1^{-1} \circ ... \circ W_n^{-1} $$
Collision probabilities:
$$ p_{\color{red}{a} \rightarrow \color{blue}{b}, k}(\mathbf{s}) = ( \mathbf{W}^{-1} \circ I \circ \mathbf{W} ) (\mathbf{s}), \\ \overrightarrow \nabla \cdot p_{\color{red}{a} \rightarrow \color{blue}{b}, k}(\mathbf{s}) = ( \mathbf{W}^{-1} \circ (\overrightarrow \nabla \cdot I ) \circ \mathbf{W} ) (\mathbf{s}). $$

Overview

Overview
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Top-down view.
Perspective view.
3 - Union.
  • until now: 1 agent
  • now: all agents
Classical probability union operation.
Collision probabilities with everyone:
$$ p_{a \rightarrow \mathcal{A} \setminus a, k} $$
And gradients:
$$ \overrightarrow \nabla \cdot p_{a \rightarrow \mathcal{A} \setminus a, k} $$

Overview

Overview
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Top-down view.
Perspective view.
4 - Movement solution.
  • gather collision probabilities along projected trajectory
Probabilities & gradients along $\mathbf{r}_{a, k}$:
$$ \begin{align} p_{a, k} &= \frac{1}{N_{a, k}} \int_{t} p_{a \rightarrow \mathcal{A} \setminus a, k}(\mathbf{r}_{a, k}(t))^2 \\ \overrightarrow \nabla \cdot p_{a, k} &= \frac{1}{N_{a, k}} \int_{t} p_{a \rightarrow \mathcal{A} \setminus a, k}(\mathbf{r}_{a, k}(t))\: (\overrightarrow \nabla \cdot p_{a \rightarrow \mathcal{A} \setminus a, k})(\mathbf{r}_{a, k}(t)) \end{align} $$
With the normalization factor:
$$ N_{a, k} = \int_{t} p_{a \rightarrow \mathcal{A} \setminus a, k}(\mathbf{r}_{a, k}(t)) $$

Overview

Overview
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Top-down view.
Perspective view.
4 - Movement solution.
  • gather collision probabilities along projected trajectory
  • compute application point
  • 1 step of gradient descent
Application point:
$$ \mathbf{s}_{a, k} = \frac{1}{N_{a, k}} \int_{t} p_{a \rightarrow \mathcal{A} \setminus a, k}(\mathbf{r}_{a, k}(t))\: \mathbf{r}_{a, k}(t) $$
Compute new trajectory $\mathbf{r}_{a, k}^*$:
$$ \mathbf{r}_{a, k}^* = line(\mathbf{o},\: \mathbf{s}_{a, k} - \alpha p_{a, k} \overrightarrow \nabla \cdot p_{a, k}) $$

Overview

Overview
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Some warp operators:

Figure: Junction.

Figure: Curved path.

Figure: Observed motion.

Figure: Obstacle interaction.

Results

Results
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Evaluation on "old", known data with our evaluation framework:

Results

Results
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Evaluation in more challenging situations
  • side-by-side comparisons with a typical second-order algorithm (ORCA)
  • more detailed/rigorous analysis in manuscript

Results - 1/8 Big groups

Results
1/8 Big groups
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion

Results - 2/8 Crossing

Results
2/8 Crossing
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion

Results - 3/8 Curved flows

Results
3/8 Curved flows
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion

Results - 3/8 Curved flows

Results
3/8 Curved flows
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion

Results - 4/8 Curved obstacle

Results
4/8 Curved obstacle
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion

Results - 4/8 Curved obstacle

Results
4/8 Curved obstacle
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion

Results - 5/8 Wall interaction

Results
5/8 Wall interaction
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Older man => scripted behavior.

Results - 6/8 Narrow zig-zags

Results
6/8 Narrow zig-zags
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Woman in middle => scripted behavior.

Results - 7/8 Danger corridor

Results
7/8 Danger corridor
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion

Results - 8/8 Plane egress

Results
8/8 Plane egress
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion

Conclusion - Summary

Conclusion
Summary
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
A new collision-avoidance algorithm
  • probabilistic
  • advanced, non-linear collision prediction from:
    • position
    • velocity
    • environmental information
    • past behaviors
  • much improves simulation results
    • in well-studied situations
    • more challenging situations

Conclusion - Limitations, future work

Conclusion
Limitations, future work
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Limitations
  • the environment has to be annotated
  • computationally expensive
    • quadratic complexity
    • single-threaded

Conclusion - Limitations, future work

Conclusion
Limitations, future work
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Limitations
  • the environment has to be annotated
  • computationally expensive now faster
    • quadratic complexity linear complexity
    • single-threaded multi-threaded

Conclusion - Limitations, future work

Conclusion
Limitations, future work
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Overview
  3. Results
  4. Conclusion
Future work
  • notion of dangerousness
  • other behaviors to explore:
    • following
    • fleeing
    • group behaviors

Outline

Outline
1 - Related Work
2 - Two main contributions:
Evaluation
An evaluation framework
automatic tuning of algorithms -
data-based -
general -
Simulation
New collision-avoidance algorithm
- advanced collision prediction
- probabilistic
- easily extensible
3 - Secondary contributions:
Applications of evaluation framework
- insect simulation
- pedestrian tracking

Applications of Evaluation Framework

Introduction

Introduction
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Insect Simulation
  3. Pedestrian Tracking
Evaluation framework
  • previousy used for:
    • evaluation of simulation algorithms
    • helping users achieve simulation goals
  • now, used as an algorithm selector:
    • per-simulation: insect simulation
    • per-moment: pedestrian tracking

Insect simulation - Introduction

Insect simulation
Introduction
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Insect Simulation
  3. Pedestrian Tracking
Collaboration
With Weizi Li (lead), PhD student at the Gamma Group from the University of North Carolina, USA.
Position
  • Existing work: little validation against reference data (lack of data)
  • With recent availability of such data: we propose a data-driven approach

Insect simulation - Results

Insect simulation
Results
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Insect Simulation
  3. Pedestrian Tracking
The data [PKO14]:

Insect simulation - Approach

Insect simulation
Approach
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Insect Simulation
  3. Pedestrian Tracking
Proposed system:
Low level:
Optimize simulation algorithms, select best one.
Intermediate level:
Statistically recreate noisy insect trajectories.
High level:
Use Metropolis-Hastings criterion to enforce density and boundaries.

Insect simulation - Results

Insect simulation
Results
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Insect Simulation
  3. Pedestrian Tracking

Insect simulation - Results

Insect simulation
Results
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Insect Simulation
  3. Pedestrian Tracking

Figure: Metric polarization factor.

Insect simulation - Results

Insect simulation
Results
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Insect Simulation
  3. Pedestrian Tracking

Pedestrian tracking - Introduction

Pedestrian tracking
Introduction
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Insect Simulation
  3. Pedestrian Tracking
Collaboration
With Aniket Bera (lead), PhD student at the Gamma Group from the University of North Carolina, USA.
Position
  • Use existing approach: simulator + particle filter tracking algorithm
  • Replace single simulator by meta-simulator

Pedestrian tracking - Approach

Pedestrian tracking
Approach
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Insect Simulation
  3. Pedestrian Tracking
Central equation of a particle filter:
$$ p(x_{t} | y_{t-k:t}) \approx \alpha p(y_{t} | x_{t}) \sum_{i=1}^{n}{\pi_{t-1}^{(i)}p(x_{t} | x_{t-1}^{(i)})} $$
$$ p(x_{t} | y_{t-k:t}) \approx \alpha p(y_{t} | x_{t}) \sum_{i=1}^{n}{\pi_{t-1}^{(i)}\color{red}{p(x_{t} | x_{t-1}^{(i)})}} $$
The red term is the motion prior.
  • usually computed thanks to a (single) simulation algorithm
  • we use several concurrent algorithms
    • we optimize them
    • we select the best one at every timestep
=> More accurate computation of the motion prior.

Pedestrian tracking - Results

Pedestrian tracking
Results
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Insect Simulation
  3. Pedestrian Tracking

Figure: Evaluation datasets.

Pedestrian tracking - Results

Pedestrian tracking
Results
  1. Evaluation and Parameter Estimation
  2. Collision Avoidance Algorithm
  3. Applications of Evaluation Framework
  1. Introduction
  2. Insect Simulation
  3. Pedestrian Tracking
Results
  • tested on various publically available datasets:
    • Low density: NDLS-2, NPLC-2, seq_hotel, seq_eth, zara01, zara02
    • Medium density: NPLC-1, NPLC-3, IITF-2, IITF-4
    • High density: NDLS-1, IITF-1, IITF-3, IITF-5
  • we consistently outperform other methods
  • tracking achieved in real-time

Conclusion

Conclusion

Conclusion
1 - Related Work
2 - Two main contributions:
Evaluation
An evaluation framework
automatic tuning of algorithms -
data-based -
general -
Simulation
New collision-avoidance algorithm
- advanced collision prediction
- probabilistic
- easily extensible
3 - Secondary contributions:
Applications of evaluation framework
- insect simulation
- pedestrian tracking

Future direction

Future direction
  • use WarpDriver with our tracking approach
    • solidify tracking
    • more easily collect more data
  • use this data with Craal and WarpDriver
    • evaluate, improve WarpDriver
    • learn context-dependent parameters
  • use these parameters
    • varying during the simulation, per context
=> Push agent-based simulation towards data-driven territory.

Publications

Publications
D. Wolinski, S.J. Guy, A.-H. Olivier, M. Lin, D. Manocha, J. Pettré
Parameter estimation and comparative evaluation of crowd simulations
Computer Graphics Forum, 2014
D. Wolinski, S.J. Guy, A.-H. Olivier, M. Lin, D. Manocha, J. Pettré
Optimization-based Pedestrian Model Calibration for Evaluation
Transportation Research Procedia, 2014
W. Li, D. Wolinski, J. Pettré, M. Lin
Biologically-Inspired Visual Simulation of Insect Swarms
Computer Graphics Forum, 2015
A. Bera, D. Wolinski, J. Pettré, D. Manocha
Real-time Crowd Tracking using Parameter Optimized Mixture of Motion Models
In preparation for Transportation Research.
D. Wolinski, M. Lin, J. Pettré
WarpDriver: Context-Aware Probabilistic Motion Prediction for Crowd Simulation
In preparation for Transactions on Graphics.

Thank you for your attention!